
type dim = int;;
type row = int;;
type col = int;;
type square = row * col;;
type board = (row*col) list;;

let ( ** ) f g x = f(g x);;

let attacks : square -> square -> bool =
  fun (x1, y1) (x2, y2) -> 
    x1 = x2 || y1 = y2 || abs(x1-x2) = abs(y1-y2);;

let legal1 : square -> board -> bool =
  fun sq sqs -> List.for_all (not ** attacks sq) sqs;;

let rec findq : col -> row -> dim -> board -> board option =
  fun c r d b -> 
    match c, r with
     | 0, _ -> Some b
     | _, 0 -> None 
     | _, _ -> if not(legal1 (r,c) b) then findq c (r-1) d b
       else 
         match findq (c-1) d d ((r,c)::b) with
          | None -> findq c (r-1) d b
          | b -> b;; 

let queens : dim -> board option = 
  fun d -> findq d d d [];;

 
